/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-07
 * Time: 11:27
 */
public class Solution {
    static class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        //处理边界
        if (pRootOfTree == null) {
            return null;
        }
        TreeToLinkedList(pRootOfTree);
        TreeNode cur = pRootOfTree;
        //找出当前链表的头节点
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }

    //记录前一个节点
    public  TreeNode prev = null;
    public  void TreeToLinkedList(TreeNode root) {
        if (root == null) {
            return;
        }
        //遍历左树
        TreeToLinkedList(root.left);

        //令当前结点指向前一个结点
        root.left = prev;

        //当前一个结点不为空时，令前一个结点指向当前结点
        if (prev != null) {
            prev.right = root;
        }
        //更新prev
        prev = root;
        //遍历右树
        TreeToLinkedList(root.right);
    }
}
